<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
    <style>
        body{
            padding: 0;
            margin: 0;
            border: none;
            overflow: hidden;
        }
        .cell {
            font-size: 40px;
            border: 3px solid;
            width: 84px;
            height: 84px;
            line-height: 90px;
            text-align: center;
            background: aliceblue;
        }
    </style>
</head>
<body>
<button onclick="nextLog()">Next</button>&nbsp;&nbsp;&nbsp;&nbsp;<button onclick="autoNextLog()">Auto Next</button>
<table id="table">
    <tbody id="tbody"></tbody>
</table>
<textarea id="input" style="width: 100vw;" rows="5"></textarea>
</body>
<script>
    class shudu {
        // 9 个 9*9 的索引
        static jiu = {
            0: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]],
            1: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1]]),
            2: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1]]),
            3: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0],_[1] + 3]),
            4: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1] + 3]),
            5: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1] + 3]),
            6: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0],_[1] + 6]),
            7: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1] + 6]),
            8: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1] + 6]),
        };
        // fn(n,x,y)
        static print(arr,fn) {
            let tmp = "";
            fn = fn || (x => x + "\t");
            for (let i = 0;i < 9;i++) {
                tmp = "";
                for (let j = 0;j < 9;j++) {
                    tmp += fn(arr[i][j],j,i);
                }
                console.log(tmp);
            }
        }
        constructor(board) {
            // 记录 9 * 9 个格子里装了什么
            this.content = [];
            // 记录 没填空的格子能填什么 9*9*n
            this.ok = {
                // "03": {
                //     lind: 0,
                //     nind: 3,
                //     arr: []
                // }
            };
            this._ok = [];
            this.init(board);
            this.log = [];
        }
        init(board) {
            board.forEach((line,lind) => {
                this.content.push([]);
                line.forEach((num,nind) => {
                    if (num === '.') {
                        this.content[lind].push(0);
                        this.ok[`${lind}${nind}`] = {
                            jiu: parseInt(lind / 3) * 3 + parseInt(nind / 3),
                            lind: lind,
                            nind: nind,
                            arr: [],
                            selectInd: 0
                        };
                    } else {
                        this.content[lind].push(+num);
                    }
                });
            });
            let t = '';
            for (let okInd in this.ok) {
                let ok = this.ok[okInd];
                let has = [];
                shudu.jiu[ok.jiu].forEach(xy => {
                    t = board[xy[1]][xy[0]];
                    if (t !== '.') {
                        has.push(t);
                    }
                });
                for (let i = 0;i < 9;i++) {
                    t = this.content[i][ok.nind];
                    if (t !== 0 && !has.includes(t)) {
                        has.push(t);
                    }
                    t = this.content[ok.lind][i];
                    if (t !== 0 && !has.includes(t)) {
                        has.push(t);
                    }
                }
                has = has.map(_ => +_);
                for (let i = 1;i <= 9;i++) {
                    if (!has.includes(i)) {
                        this.ok[okInd].arr.push(i);
                    }
                }
            }
            for (let okInd in this.ok) {
                let ok = this.ok[okInd];
                if (ok.arr.length === 1) {
                    this.content[ok.lind][ok.nind] = ok.arr[0];
                    delete this.ok[okInd];
                } else {
                    this._ok.push(ok);
                }
            }
            // shudu.print(this.content,(n,x,y) => {
            //     if (`${y}${x}` in this.ok) {
            //         return this.ok[`${y}${x}`].arr.join('') + '\t';
            //     } else {
            //         return `${n}\t`;
            //     }
            // });
        }

        check(y,x,jiu,n) {
            let ok = true;
            let _jiu = shudu.jiu[jiu];
            for (let i = 0;ok && i < 9;i++) {
                if (this.content[y][i] === n || this.content[i][x] === n || this.content[_jiu[i][1]][_jiu[i][0]] === n) {
                    if (this.content[y][i] === n) {
                        this.log.push({
                            type: 'error',
                            x: i,
                            y: y,
                            n: n,
                            ok: false
                        });
                    } else if (this.content[i][x] === n) {
                        this.log.push({
                            type: 'error',
                            x: x,
                            y: i,
                            n: n,
                            ok: false
                        });
                    } else {
                        this.log.push({
                            type: 'error',
                            x: _jiu[i][0],
                            y: _jiu[i][1],
                            n: n,
                            ok: false
                        });
                    }
                    ok = false;
                }
            }
            return ok;
        }
        // 回溯算法
        getResult() {
            this.log = [];
            let test = (okInd) => {
                if (okInd >= this._ok.length) {
                    return true;
                } else {
                    let ok = this._ok[okInd];
                    console.log(`okInd = ${okInd}\tx = ${ok.nind}\ty = ${ok.lind}`);
                    this.content[ok.lind][ok.nind] = 0;
                    for (let i = 0;i < ok.arr.length;i++) {
                        this.log.push({
                            type: 'before',
                            x: ok.nind,
                            y: ok.lind,
                            n: ok.arr[i],
                            // ok: true
                        });
                        if (this.check(ok.lind,ok.nind,ok.jiu,ok.arr[i])) {
                            this.log.push({
                                type: 'check',
                                x: ok.nind,
                                y: ok.lind,
                                n: ok.arr[i],
                                ok: true
                            });
                            this.content[ok.lind][ok.nind] = ok.arr[i];
                            if (test(okInd + 1)) {
                                this.content[ok.lind][ok.nind] = 0;
                                return true;
                            }
                        } else {
                            this.content[ok.lind][ok.nind] = 0;
                            this.log.push({
                                type: 'check',
                                x: ok.nind,
                                y: ok.lind,
                                n: ok.arr[i],
                                ok: false
                            });
                        }
                    }
                    this.content[ok.lind][ok.nind] = 0;
                    return false;
                }
            };
            if (this._ok.length) {
                test(0);
            } else {
                return
            }
        }
    }
</script>
<script>
    let sd;// = new shudu()
    function buildTable() {
        let html = "";
        let table = document.getElementById('tbody');
        for (let i = 0;i < 9;i++) {
            html += `<tr>`;
            for (let j = 0;j < 9;j++) {
                html += `<td class="cell" id="cell_${i}${j}"></td>`
            }
            html += `</tr>`;
        }
        table.innerHTML = html;
    }
    window.cells = [];
    window.onload = function () {
        window.log = document.getElementById('log');
        document.getElementById('input').value = JSON.stringify([
            ["5","3",".",".","7",".",".",".","."],
            ["6",".",".","1","9","5",".",".","."],
            [".","9","8",".",".",".",".","6","."],
            ["8",".",".",".","6",".",".",".","3"],
            ["4",".",".","8",".","3",".",".","1"],
            ["7",".",".",".","2",".",".",".","6"],
            [".","6",".",".",".",".","2","8","."],
            [".",".",".","4","1","9",".",".","5"],
            [".",".",".",".","8",".",".","7","9"]
        ]);
        buildTable();
        sd = new shudu(JSON.parse(document.getElementById('input').value));
        shudu.print(sd.content,function (n,x,y) {
            if (n !== 0) {
                let cell = document.getElementById(`cell_${y}${x}`);
                cell.innerHTML = n;
                cell.style.background = "black";
                cell.style.color = 'white';
            }
        });
        sd.getResult();
        for (let i = 0;i < 9;i++) {
            cells.push([]);
            for (let j = 0;j < 9;j++) {
                cells[i].push(document.getElementById(`cell_${i}${j}`));
            }
        }
    }
    window.logPoint = 0;
    window.nextLog = function () {
        if (window.logPoint < sd.log.length) {
            cells.forEach((cs,y) => {
                cs.forEach((cl,x) => {
                    cl.style.borderColor = 'black'
                    // if (sd.content[y][x] === 0) {
                    //     cl.style.background = 'aliceblue';
                    //     cl.innerText = '';
                    // }
                });
            });
            let log = sd.log[window.logPoint];
            window.logPoint++;
            let cell = cells[log.y][log.x];
            if (log.type === 'check') {
                cell.style.background = log.ok ? 'green' : 'red';
                cell.innerText = log.n;
            } else if (log.type === 'error') {
                cell.style.borderColor = 'red';
            } else if (log.type === 'before') {
                cell.style.background = 'blue';
                cell.innerText = log.n;
            }
            return true;
        } else {
            return false;
        }
    }
    window.autoNextLog = function () {
        let id = setInterval(() => {
            let ok = window.nextLog();
            if (!ok) {
                clearInterval(id);
            }
        },100);
    }
</script>
</html>
